﻿using System;
using System.Collections.Generic;

public class BinaryNode<T> where T : IComparable<T> {
    private T data;
    private BinaryNode<T> left;
    private BinaryNode<T> right;

    public BinaryNode() { }

    public BinaryNode(T data) {
        this.data = data;
    }

    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T Value {
        get { return data; }
        set { data = value; }
    }

    public BinaryNode<T> Right {
        get { return right; }
        set { right = value; }
    }

    public BinaryNode<T> Left {
        get { return left; }
        set { left = value; }
    }

    public string ToTree(string blank, string spacing) {
        string s = "" + data + "\n";
        if (left == null)
            s += spacing + default(T) + "\n";
        else
            s += spacing + left.ToTree(blank, blank + spacing);
        if (right == null)
            s += spacing + default(T) + "\n";
        else
            s += spacing + right.ToTree(blank, blank + spacing);
        return s;
    }

    public bool isLeaf() {
        return (left == null) && (right == null);
    }

    public int getHeight() {
        return getHeight(this);
    }

    private int getHeight(BinaryNode<T> node) {
        // bottom of tree: height==0
        if (node == null)
            return 0;
        // node to children adds 1 to height of node:
        else
            return 1 + Math.Max(getHeight(node.left), getHeight(node.right));
    }

    public override string ToString() {
        return GetType().Name;
    }

    public bool naivefind(T target, BinaryNode<T> n) {
        if (n == null)
            return false;
        else
            return target.Equals(n.Value) || naivefind(target, n.Left) || naivefind(target, n.Right);
    }
}


